package leetcode.median;

/**
 * ClassName: $200_NumIslands
 * Description:
 * date: 2022-02-17 17:23
 *
 * @author liyifan
 */
public class $200_NumIslands {

    public int numIslands(char[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        int res = 0;
        for (int i = 0;i < rows;i++) {
            for (int j = 0;j < cols;j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    res++;
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid, int r, int c){
        if (!isArea(grid, r, c)) return;
        if (grid[r][c] != '1') return;

        grid[r][c] = '2';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    int rows;
    int cols;
    public boolean isArea(char[][] grid, int r, int c){
        return r >= 0 && r < rows && c >=0 && c < cols;
    }


    public int numIslands1(char[][] grid) {
        rows = grid.length;
        cols = grid[0].length;
        boolean[][] vis = new boolean[rows][cols];
        int res = 0;
        for (int i = 0;i < rows;i++) {
            for (int j = 0;j < cols;j++) {
                if (!vis[i][j] && grid[i][j] == '1') {
                    dfs1(grid, i, j, vis);
                    res++;
                }
            }
        }
        return res;
    }

    public void dfs1(char[][] grid, int r, int c, boolean[][] vis){
        if (!isArea(grid, r, c)) return;
        if (grid[r][c] != '1') return;
        vis[r][c] = true;
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

}
